package com.zhangxiaofanfan.hotcode.fourth.third;

import java.util.HashSet;
import java.util.Set;

/**
 * <a href="https://leetcode.cn/problems/number-of-islands/description/?envType=study-plan-v2&envId=top-100-liked">200. 岛屿数量</a>
 *
 * @author zhangxiaofanfan
 * @date 2024-06-26 20:33:33
 */
public class HotCode051 {
    public static void main(String[] args) {
        char[][] grid = {
                {'1', '1', '1', '1', '0'},
                {'1', '1', '0', '1', '0'},
                {'1', '1', '0', '0', '0'},
                {'0', '0', '0', '1', '1'}
        };
        HotCode051 hotCode = new HotCode051();
        System.out.println(hotCode.numIslands(grid));
    }

    public int numIslands(char[][] grid) {
        int row = grid.length, col = grid[0].length, rowIndex, colIndex, areaCount = 0;
        Set<Integer> setArrived = new HashSet<>();
        for (rowIndex = 0; rowIndex < row; rowIndex++) {
            for (colIndex = 0; colIndex < col; colIndex++) {
                int index = rowIndex * col + colIndex;
                if (!setArrived.contains(index) && grid[rowIndex][colIndex] == '1') {
                    bfs(grid, rowIndex, colIndex, setArrived);
                    areaCount++;
                }
            }
        }
        return areaCount;
    }

    public void bfs(char[][] grid, int rowIndex, int colIndex, Set<Integer> setArrived) {
        if (rowIndex < 0 || rowIndex >= grid.length || colIndex < 0 || colIndex >= grid[0].length) {
            return;
        }
        if (grid[rowIndex][colIndex] == '0') {
            return;
        }
        int index = rowIndex * grid[0].length + colIndex;
        if (setArrived.contains(index)) {
            return;
        }
        setArrived.add(index);
        bfs(grid, rowIndex - 1, colIndex, setArrived);
        bfs(grid, rowIndex + 1, colIndex, setArrived);
        bfs(grid, rowIndex, colIndex + 1, setArrived);
        bfs(grid, rowIndex, colIndex - 1, setArrived);
    }
}
